// https://leetcode.cn/problems/additive-number/
// Created by ade on 2022/10/18.
//
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    // 核心思路：三指针
    bool isAdditiveNumber(string num) {
        int len = num.size();
        if (len < 3) return false;
        int maxL = 0;
        for (int l = 0; l <= len - 3; l++) {
            bool flag = false;
            for (int m = l + 1; m <= len - 2; m++) {
                if (m - l > 1 && num[l] == '0') continue;
                for (int r = m + 1; r <= len - 1; r++) {
                    if (r - m > 1 && num[m] == '0') continue;
                    vector<char> res = add(num, l, m, r);
                    int resLen = res.size();
                    if (r + resLen > len) break;
                    int cflag = 1;
                    for (int i = 0; i < resLen; i++)
                        if (res[i] != num[r + i]) {
                            cflag = 0;
                            break;
                        }
                    if (cflag == 0) continue;
                    if (r + resLen == len) {

                        return true;
                    }
                    flag = true;
                    maxL = max(maxL, m);
                }
            }
            if (!flag && l >= maxL) return false;
        }

        return false;
    }

    void dfs(string &num, int l, int m, int r, bool &flag) {
        if (m - l > 1 && num[l] == '0' || r - m > 1 && num[m] == '0') return;
        vector<char> res = add(num, l, m, r);
        int resLen = res.size();
        if (r + resLen > len) return;
        for (int i = 0; i < resLen; i++)
            if (res[i] != num[r + i]) return;

        if (r + resLen == len) {
            flag = true;
            return;
        }

        l = l + 1;
        for (int tm = l + 1; tm <= len - 2; tm++) {
            for (int tr = tm + 1; tr <= len - 1; tr++) {
                dfs(num, l, tm, tr, flag);
                if (flag) return;
            }
        }
    }

    // 左闭右开原则 [l, m-1] 左侧  [m, r-1] 右侧
    vector<char> add(string &num, int l, int m, int r) {
        vector<char> res = {};
        int maxSize = max(m - l, r - m);
        int flag = 0; // 进位标志符
        for (int i = 0; i < maxSize; i++) {
            int tmp = flag;
            if (i < m - l) tmp += num[m - 1 - i] - '0';
            if (i < r - m) tmp += num[r - 1 - i] - '0';
            if (tmp >= 10) {
                tmp -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
            res.push_back(tmp + '0');
        }
        if (flag) res.push_back('1');
        reverse(res.begin(), res.end());
//        cout << "l:" << l << ",m:" << m << ",r:" << r;
//        cout << "res:" << endl;
//        for (auto &i:res) {
//            cout << i;
//        }
//        cout << endl;
        return res;
    }

};

int main() {
    Solution so;
//    string s = "120122436";
//    string s = "1980198239625944";
    string s = "1991000199299498797";
    cout << so.isAdditiveNumber(s);

    return 0;
}